class Solution(object):
    def containVirus(self, isInfected):
        m = len(isInfected)
        n = len(isInfected[0])

        used = [[0 for _ in range(n)] for _ in range(m)]
        ans = 0

        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    p[rooty] = rootx
                    nums[rootx] += nums[rooty] - 2
                    nums[rooty] = 0
                    weixie[rootx].update(weixie[rooty])
                    weixie[rooty] = set()
                else:
                    p[rootx] = rooty
                    nums[rooty] += nums[rootx] - 2
                    nums[rootx] = 0
                    weixie[rooty].update(weixie[rootx])
                    weixie[rootx] = set()
            else:
                nums[rootx] -= 2

        while True:
            nums = [0] * m * n
            weixie = [set() for _ in range(m * n)]
            p = [i for i in range(m * n)]
            for i in range(m):
                for j in range(n):
                    if isInfected[i][j] and not used[i][j]:
                        t = 4
                        if i == 0:
                            t -= 1
                        if i == m - 1:
                            t -= 1
                        if j == 0:
                            t -= 1
                        if j == n - 1:
                            t -= 1
                        if i > 0 and used[i - 1][j]:
                            t -= 1
                        if i < m - 1 and used[i + 1][j]:
                            t -= 1
                        if j > 0 and used[i][j - 1]:
                            t -= 1
                        if j < n - 1 and used[i][j + 1]:
                            t -= 1
                        nums[i * n + j] = t
                        for ux, uy in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
                            if 0 <= ux < m and 0 <= uy < n and used[ux][uy] == 0 and isInfected[ux][uy] == 0:
                                weixie[i * n + j].add((ux, uy))
                        if i > 0:
                            if isInfected[i - 1][j] and not used[i - 1][j]:
                                union((i - 1) * n + j, i * n + j)
                        if j > 0:
                            if isInfected[i][j - 1] and not used[i][j - 1]:
                                union(i * n + j - 1, i * n + j)
            max_val = 0
            max_index = -1
            for i in range(m * n):
                if len(weixie[i]) > max_val:
                    max_val = len(weixie[i])
                    max_index = i
            if max_val == 0:
                return ans
            ans += nums[max_index]
            max_i, max_j = max_index // n, max_index % n
            used[max_i][max_j] = 1
            now = {(max_i, max_j)}
            while now:
                x, y = now.pop()
                for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= ux < m and 0 <= uy < n and used[ux][uy] == 0 and isInfected[ux][uy] == 1:
                        used[ux][uy] = 1
                        now.add((ux, uy))
            for i in range(m * n):
                if i != max_index and weixie[i]:
                    for ux, uy in weixie[i]:
                        isInfected[ux][uy] = 1



data = Solution()
isInfected = [[0, 1, 0, 0, 0, 1], [0, 1, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]
print(data.containVirus(isInfected))
isInfected = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
print(data.containVirus(isInfected))
isInfected = [[1, 1, 1, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 0, 0, 0]]
print(data.containVirus(isInfected))
